class Solution {
public:
    vector<int> partitionLabels(string S) {
       /*
       S=S+"A";
       vector<int> ans;
       int left_tmp=S.find_first_of(S[0]);
       int right_tmp=S.find_last_of(S[0]);
       int left=left_tmp;
       int right=right_tmp;

       for(int i=1;i<S.size();i++){
           left_tmp=S.find_first_of(S[i]);
           right_tmp=S.find_last_of(S[i]);
           if(left<=left_tmp&&left_tmp<=right){
               left=left<=left_tmp?left:left_tmp;
               right=right>=right_tmp?right:right_tmp;
               //cout<<"left:"<<left<<",right:"<<right<<endl;
           } else{
               ans.push_back(right-left+1);
               //cout<<"cluster len:"<<right-left+1<<endl;
               left=left_tmp;
               right=right_tmp;
           }
       } 
       return ans;
       */
       
       S=S+"A";
       vector<int> ans;
       unordered_map<char,int> dict;
       for(int i=0;i<S.size();i++){
           dict[S[i]]=i;
       }
       int begin=0;
       int end=0;
       for(int i=0;i<S.size();i++){
           if(i>end){
               ans.push_back(end-begin+1);
               begin=i;
               end=dict[S[i]];
           } else{
               if(dict[S[i]]>end){
                   end=dict[S[i]];
               }
           }
       }
       return ans;
    }
};